/*
 编程实现二叉排序树
1)插入结点，删除结点；
2 对二叉排序树进行前序、中序、和后序非递归遍历;
3) 查找某个结点是否存在，如果能找到在屏幕上打印存在结点，否则打印不存
 */

#include<iostream>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<math.h>

using namespace std;
typedef int DataType;

//结点类
class BinTreeNode
{
    friend class BinaryTree;
    DataType data;
    int level; //层级
    int leftRight; //1:左，2：右
    BinTreeNode *leftChild,*rightChild;
};

struct VistedNode
{
    BinTreeNode* node;
    bool vistedRightChild=false;
};

class BinaryTree {
private:
    BinTreeNode *root;
    int inputValue;
public:
    BinaryTree() : root(NULL) {
    }

    BinaryTree(BinaryTree &s);

    ~BinaryTree() {
        destroy(root);
    }

    void CreateBinTree(BinTreeNode *&subTree, int level, int leftRight);

    void CreateBinTree();

    BinTreeNode *Find(BinTreeNode *&node, DataType &item);

    BinTreeNode *Find(DataType &item);

    void destroy(BinTreeNode *&tree);

    int Height(BinTreeNode *subTree);

    void MiddleOrder();//非递归的中序遍历
    void FirstOrder();//非递归的前序遍历
    void LastOrder();//非递归的后序遍历
    void Insert(DataType data);

    void InsertData();

    BinTreeNode *FindMinLevelNoChildrenNode();

    void FindNoChildrenNode(BinTreeNode *&node, BinTreeNode *&noChildrenNode);

    bool Delete(BinTreeNode *&node, DataType data);

    void DeleteData();

    void FindAndPrintTree();

    void PrintTree(BinTreeNode *node);
};

BinTreeNode *BinaryTree::Find(BinTreeNode *&node, DataType &item) {
    if (node == NULL) return NULL;

    if (node->data == item) return node;

    BinTreeNode *dataNode = NULL;
    if (node->leftChild != NULL && node->leftChild->level > 0) {
        dataNode = Find(node->leftChild, item);
    }
    if (dataNode == NULL && node->rightChild != NULL && node->rightChild->level > 0) {
        dataNode = Find(node->rightChild, item);
    }
    return dataNode;
}

BinTreeNode *BinaryTree::Find(DataType &item) {
    return Find(root, item);
}

bool BinaryTree::Delete(BinTreeNode *&node, DataType data) {
    if (node == NULL) return false;

    if (node->data == data) {
        cout << "删除结点：<" << node->level << "," << node->data << "," << node->leftRight << ">" << endl;

        delete node;
        node = NULL;
        return true;
    }

    bool blSucceed = false;
    if (node->leftChild != NULL && node->leftChild->level > 0) {
        blSucceed = Delete(node->leftChild, data);
    }
    if (!blSucceed && node->rightChild != NULL && node->rightChild->level > 0) {
        blSucceed = Delete(node->rightChild, data);
    }
    return blSucceed;
}

void BinaryTree::FindNoChildrenNode(BinTreeNode *& node, BinTreeNode *&noChildrenNode) {
    if (node != NULL && node->level > 0) {
        if (node->leftChild == NULL || node->rightChild == NULL
            || node->leftChild->level < 0 || node->rightChild->level < 0) {
            if (noChildrenNode == NULL || noChildrenNode->level > node->level) noChildrenNode = node;
        }
        if (node->leftChild != NULL && (noChildrenNode == NULL || noChildrenNode->level > node->leftChild->level)) {
            FindNoChildrenNode(node->leftChild, noChildrenNode);
        }
        if (node->rightChild != NULL &&
            (noChildrenNode == NULL || noChildrenNode->level > node->rightChild->level)) {
            FindNoChildrenNode(node->rightChild, noChildrenNode);
        }
    }
}

BinTreeNode *BinaryTree::FindMinLevelNoChildrenNode() {
    BinTreeNode *noChildrenNode = NULL;
    FindNoChildrenNode(root, noChildrenNode);
    return noChildrenNode;
}

void BinaryTree::Insert(DataType data) {
    //1、找到最小层级没有的结点
    BinTreeNode *parentNode = FindMinLevelNoChildrenNode();
    if (parentNode != NULL) {
        BinTreeNode *node = new BinTreeNode();
        node->data = data;
        node->level = parentNode->level + 1;
        if (parentNode->leftChild == NULL || parentNode->leftChild->level < 0) {
            node->leftRight = 1;
            parentNode->leftChild = node;
        }
        else if (parentNode->rightChild == NULL || parentNode->rightChild->level < 0) {
            node->leftRight = 2;
            parentNode->rightChild = node;
        }
        if (node->leftRight > 0) {
            cout << "插入结点成功" << endl;
            cout << "父级结点：<" << parentNode->level << "," << parentNode->data << "," << parentNode->leftRight << ">"
                 << endl;
            cout << "当前结点：<" << node->level << "," << node->data << "," << node->leftRight << ">" << endl;
        } else cout << "插入结点失败" << endl;
    } else cout << "获取父级结点失败" << endl;
}

void BinaryTree:: InsertData() {
    DataType data;
    cout<<"请输入插入结点数据(输入小于或等于0的值结束):"<<endl;
    cin>>data;

    while(data>0)
    {
        this->Insert(data);
        cout<<"请输入插入结点数据(输入小于或等于0的值结束):"<<endl;
        cin>>data;
    }
}

void BinaryTree::DeleteData() {
    DataType data;
    cout << "请输入删除结点数据(输入小于或等于0的值结束):" << endl;
    cin >> data;

    while (data > 0) {
        if (this->Delete(root, data))cout << "删除成功" << endl;
        else cout << "查无此结点，无法删除" << endl;
        cout << "请输入删除结点数据(输入小于或等于0的值结束):" << endl;
        cin >> data;
    }
}

void  BinaryTree::FindAndPrintTree(){
    DataType data;
    cout << "请输入查找结点数据(输入小于或等于0的值结束):" << endl;
    cin >> data;

    while (data > 0) {
        BinTreeNode *node = Find(data);
        if(node==NULL) cout << "查找结点不存在" << endl;
        else {
            cout << "查找成功，结点：<" << node->level << "," << node->data << "," << node->leftRight << ">" << endl;
            cout << "打印此结如下:" << endl;
            PrintTree(node);
        }
        cout << "请输入查找结点数据(输入小于或等于0的值结束):" << endl;
        cin >> data;
    }
}

void BinaryTree::CreateBinTree(BinTreeNode*& subTree, int parentLevel, int leftRight) {
    DataType item;
    if (inputValue != -1) {
        cout << "请输入树结点的值:(输入0无子结点，输入-1结束)" << endl;
        cin >> item;
    } else item = -1;

    inputValue = item;
    if (item != 0 && item != -1) {
        subTree = new BinTreeNode();
        if (subTree == NULL) {
            cout << "存储分配失败" << endl;
            exit(1);
        }
        subTree->data = item;
        subTree->level = parentLevel + 1;
        subTree->leftRight = leftRight;
        CreateBinTree(subTree->leftChild, subTree->level, 1);
        CreateBinTree(subTree->rightChild, subTree->level, 2);
    } else {
        subTree = NULL;
    }
}

void BinaryTree::CreateBinTree() {
    CreateBinTree(root, 0,0);
}

void BinaryTree::destroy(BinTreeNode*& tree) {
    if (tree == NULL)
        return;
    destroy(tree->leftChild);
    destroy(tree->rightChild);
    delete tree;
    tree == NULL;
}

//非递归的中序遍历
void BinaryTree::MiddleOrder() {
    stack < BinTreeNode * > S;
    BinTreeNode *p = root;   //初始化
    do {
        while (p != NULL) {
            S.push(p);
            p = p->leftChild;//往左前进
        }
        if (!S.empty()) {                   //栈非空
            p = S.top();
            S.pop();     //退栈
            cout << "<" << p->level << "," << p->data << "," << p->leftRight << ">" << endl;
            p = p->rightChild;              //向右链走
        }
    } while (p != NULL || !S.empty());
}

//非递归的前序遍历
void BinaryTree::FirstOrder() {
    stack < BinTreeNode * > S;
    BinTreeNode *p = root;   //初始化
    do {
        while (p != NULL) {   //立刻输出p所指向的当前结点
            cout << "<" << p->level << "," << p->data << "," << p->leftRight << ">" << endl;
            //进栈之前就输出data
            S.push(p);
            p = p->leftChild;
        }
        if (!S.empty()) {                   //栈非空
            p = S.top();
            S.pop();     //退栈
            p = p->rightChild;              //向右链走
        }
    } while (p != NULL || !S.empty());
    //p==NULL   S.empty()==true
}

//非递归的后序遍历
void BinaryTree::LastOrder() {
    stack <VistedNode> S;
    BinTreeNode *p = root;   //初始化
    VistedNode vd;
    vd.node = p;
    vd.vistedRightChild = false;
    S.push(vd);
    p = p->leftChild;
    while (!S.empty()) {
        while (p != NULL) {
            vd.node = p;
            vd.vistedRightChild = false;
            S.push(vd);
            p = p->leftChild;
        }
        vd = S.top();
        if (vd.node->rightChild != NULL && vd.vistedRightChild == false) {
            S.pop();
            vd.vistedRightChild = true;
            S.push(vd);
            p = vd.node->rightChild;
        } else//如果弹出的结点是树叶或者 弹出的结点右儿子已经被访问过
        {
            S.pop();
            cout << "<" << vd.node->level << "," << vd.node->data << "," << vd.node->leftRight << ">" << endl;
            p = NULL;
        }

    }
}

int BinaryTree::Height(BinTreeNode* subTree) {
    if (subTree == NULL)
        return 0;
    else {
        int dep1 = Height(subTree->leftChild);
        int dep2 = Height(subTree->rightChild);
        if (dep1 > dep2)
            return dep1 + 1;
        else
            return dep2 + 1;
    }
}

void BinaryTree::PrintTree(BinTreeNode *node) {
    int *nodes;
    int height = Height(node);
    int TotalNodes = pow(2, Height(node));
    cout << "TotalNodes=" << TotalNodes << endl;
    nodes = new int[TotalNodes];
    int i = 1;
    DataType data;
    queue < BinTreeNode * > myqueue;
    BinTreeNode *current;
    myqueue.push(node);
    while (myqueue.empty() == false) {
        current = myqueue.front();
        if (current != NULL) {
            data = current->data;
            nodes[i] = data;
        } else
            nodes[i] = -1;
        i++;
        myqueue.pop();
        if (current != NULL) {
            myqueue.push(current->leftChild);
            myqueue.push(current->rightChild);
        }
    }
    TotalNodes = i - 1;
    int No;
    int lines = 0;
    int lineNumbers = 1;
    int MinSpace = 3;
    int TotalWidth = pow(2, Height(node) - 1) * MinSpace;
    int NodeWidth = TotalWidth / lineNumbers;
    int SpaceNumber;
    i = 1;
    int j = 0;
    int k;
    while (i <= TotalNodes) {
        No = i;
        if (No > 1 && No == pow(2, lines)) {
            for (j = i; j <= TotalNodes; j++) {
                if (j == pow(2, lines)) {
                    for (k = 0; k < NodeWidth / 2 + 1; k++)
                        cout << " ";
                } else {
                    for (k = 0; k < NodeWidth - 1; k++)
                        cout << " ";
                }
                if (nodes[j] != -1) {
                    if (j % 2 == 0)
                        cout << "/";
                    else
                        cout << "\\";
                }
                if (floor(log10(j + 1) / log10(2)) > floor(log10(j) / log10(2)) || j == TotalNodes) {
                    cout << endl;
                    break;
                }
            }
        }

        if (No == pow(2, lines)) {
            for (j = 0; j < NodeWidth / 2; j++)
                cout << " ";
        } else {
            for (j = 0; j < NodeWidth; j++)
                cout << " ";
        }
        if (nodes[i] != -1)
            cout << nodes[i];
        i++;
        if (floor(log10(No + 1) / log10(2)) > floor(log10(No) / log10(2))) {
            lines++;
            lineNumbers = pow(2, lines);
            NodeWidth = TotalWidth / lineNumbers;
            cout << endl;
        }
    }
}

int main() {
    cout << "编程实现二叉排序树" << endl;

    //1)插入结点，删除结点；
    //2 对二叉排序树进行前序、中序、和后序非递归遍历;
    //3) 查找某个结点是否存在，如果能找到在屏幕上打印存在结点，否则打印不存在
    BinaryTree bt;
    bt.CreateBinTree();
    cout << "二叉树创建完成" << endl;

    //1、插入结点
    cout << "------插入结点------" << endl;
    bt.InsertData();

    // 删除结点
    cout << "------删除结点------" << endl;
    bt.DeleteData();

    // 对二叉排序树进行前序
    cout << "------非递归的前序------" << endl;
    bt.FirstOrder();

    // 对二叉排序树进行中序
    cout << "------非递归的中序------" << endl;
    bt.MiddleOrder();

    // 对二叉排序树进行后序
    cout << "------非递归的后序------" << endl;
    bt.LastOrder();

    //查找某个结点是否存在，如果能找到在屏幕上打印存在结点，否则打印不存在
    cout << "-----查找某个结点是否存在，如果能找到在屏幕上打印存在结点，否则打印不存在------" << endl;
    bt.FindAndPrintTree();

    return 0;
}